%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2012 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% data section
\SetKwData{MyLeft}{left}
\SetKwData{MyRight}{right}
\SetKwData{MyTrue}{True}
%%
%% input
\KwIn{A binary tree $T$, given in sequence representation, having
  $n > 1$ internal vertices.}
%%
%% output
\KwOut{The binary tree $T$ heapified so that it satisfies the
  heap-order property.}
\BlankLine
%%
%% algorithm body
\For{$i \assign \lfloor n/2 \rfloor - 1, \dots, 0$}{
  $v \assign T[i]$\;
  $j \assign 0$\;
  \While{$\MyTrue$}{
    $\MyLeft \assign 2i + 1$\;
    $\MyRight \assign 2i + 2$\;
    \If{\rm $\MyLeft < n$ and $\kappa_{T[\MyLeft]} \leq \kappa_v$}{
      \If{\rm $\MyRight < n$ and $\kappa_{T[\MyRight]} \leq \kappa_{T[\MyLeft]}$}{
        $j \assign \MyRight$\;
      }
      \Else{
        $j \assign \MyLeft$\;
      }
    }
    \ElseIf{\rm $\MyRight < n$ and $\kappa_{T[\MyRight]} \leq \kappa_v$}{
      $j \assign \MyRight$\;
    }
    \Else{
      $T[i] \assign v$\;
      exit the while loop\;
    }
    $T[i] \assign T[j]$\;
    $i \assign j$\;
  }
}
\Return $T$\;
